DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2023.2

Matroid Partition Property and the Secretary Problem

Authors: Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

A matroid M on a set E of elements has the α-partition property, for some α > 0, if it is possible to (randomly) construct a partition matroid 𝒫 on (a subset of) elements of M such that every independent set of 𝒫 is independent in M and for any weight function w:E → ℝ_{≥0}, the expected value of the optimum of the matroid secretary problem on 𝒫 is at least an α-fraction of the optimum on M. We show that the complete binary matroid, B_d on 𝔽₂^d does not satisfy the α-partition property for any constant α > 0 (independent of d). Furthermore, we refute a recent conjecture of [Kristóf Bérczi et al., 2021] by showing the same matroid is 2^d/d-colorable but cannot be reduced to an α 2^d/d-colorable partition matroid for any α that is sublinear in d.

Cite as

Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Matroid Partition Property and the Secretary Problem. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abdolazimi_et_al:LIPIcs.ITCS.2023.2,
  author =	{Abdolazimi, Dorna and Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan},
  title =	{{Matroid Partition Property and the Secretary Problem}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{2:1--2:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.2},
  URN =		{urn:nbn:de:0030-drops-175051},
  doi =		{10.4230/LIPIcs.ITCS.2023.2},
  annote =	{Keywords: Online algorithms, Matroids, Matroid secretary problem}
}

Search Results

Documents authored by Klein, Nathan

Matroid Partition Property and the Secretary Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message